package com.lql.sort;

import java.util.Arrays;
import java.util.Random;

/**
 * 插入排序
 */
public class InsertSort {
    public static void main(String[] args) {
        int[] array = {1, 2, 3, 7, 0};
        int[] ints = new int[80000];
        Random random = new Random();
        for (int i = 0; i < 80000; i++) {
            ints[i] = random.nextInt(80000);
        }
        InsertSorted(array);
    }

    /**
     * 插入排序
     *
     * @param arrays 待排序的数组
     */
    public static void InsertSorted(int[] arrays) {
        long startTime = System.currentTimeMillis();
        System.out.println("开始：" + startTime);
        int insertVal;//待插入的数字
        int insertIndex;//待插入的下标索引
        //假定第一个数据是已经排好序的，从无序部分中依次拿出剩余的插入到有序部分中
        for (int i = 1; i < arrays.length; i++) {
            //定义待插入的数
            insertVal = arrays[i];
            insertIndex = i - 1; // 即arr[1]的前面这个数的下标

            // 给insertVal 找到插入的位置
            // 说明
            // 1. insertIndex >= 0 保证在给insertVal 找插入位置，不越界
            // 2. insertVal < arr[insertIndex] 待插入的数，还没有找到插入位置
            // 3. 就需要将 arr[insertIndex] 后移
            while (insertIndex >= 0 && insertVal < arrays[insertIndex]) {
                arrays[insertIndex + 1] = arrays[insertIndex];// arr[insertIndex]
                insertIndex--;
            }
            // 当退出while循环时，说明插入的位置找到, insertIndex + 1
            // 举例：理解不了，我们一会 debug
            //这里我们判断是否需要赋值
            if(insertIndex + 1 != i) {
                arrays[insertIndex + 1] = insertVal;
            }

        }
        long endTime = System.currentTimeMillis();
        System.out.println("结束：" + endTime);
        float l = (endTime - startTime) / 1000f;
        System.out.println("总时间：" + l + "秒");
        System.out.println(Arrays.toString(arrays));
    }
}
